package com.dataStructure.并查集;

/**
 * 并查集有2个核心操作
 * 查找（Find）：查找元素所在的集合（这里的集合并不是特指Set这种数据结构，是指广义的数据集合）
 * 合并（Union）：将两个元素所在的集合合并为一个集合
 */

//并查集的公共父类
public abstract class 并查集 {
    protected int[] parents;

    public 并查集(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("capacity must be >= 1 ");
        }

        parents = new int[capacity];

        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }
    }

    /**
     * 查找v所属的集合（根节点）
     * 传入的参数是parents数组的索引
     */
    public abstract int find(int v) ;

    /**
     * 合并两个集合
     */
    public abstract void union(int v1, int v2) ;

    protected void rangCheck(int v) {
        if (v < 0 || v > parents.length) {
            throw new IllegalArgumentException("");
        }
    }

    /**
     * 检查v1,v2是否属于同一个集合
     */
    public boolean isSame(int v1, int v2) {
        return find(v1) == find(v2);
    }



}
